#include <iostream>

class Node {
public:
    int data;
    Node* next;
    Node* prev;

    Node(int data):data(data),next(nullptr),prev(nullptr){}
};


class DoublyLinkedList{
private:
    Node* head;
    Node* tail;
    int size;

public:
    DoublyLinkedList():head(nullptr),tail(nullptr),size(0){}

    ~DoublyLinkedList(){
        Node* current = head;
        Node* next = nullptr;

        while(current != nullptr){
            next = current->next;
            delete current;
            current = next;
        }
        head = nullptr;
        tail = nullptr;
    }

    bool isEmpty(){
        return head == nullptr;
    }

    int getSize(){
        return size;
    }

    void insertAtHead(int data){
        Node* newNode = new Node(data);
        if(isEmpty()){
            head = newNode;
            tail = newNode;
        }else{
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
        size++;
    }

    void insertAtTail(int data){
        Node* newNode = new Node(data);
        if(isEmpty()){
            head = newNode;
            tail = newNode;
        }else{
            newNode->prev = tail;
            tail->next = newNode;
            tail = newNode;
        }
        size++;
    }

    void insertAtPosition(int data,int position){
        if(position < 0 || position > size){
            std::cout << "position is invalid" << std::endl;
            return;
        }   

        if(position == 0){
            insertAtHead(data);
            return;
        }
        if(position == size){
            insertAtTail(data);
            return;
        }

        Node* newNode = new Node(data);
        if(position <= size/2){
            Node* current = head;
            for(int i = 0; i< position;i++){
                current = current->next;
            }
            newNode->prev = current->prev;
            newNode->next = current;
            current->prev->next = newNode;
            current->prev = newNode;
        }else{
            Node* current = tail;
            for(int i = size-1;i > position;i--){
                current = current -> prev;
            }
            newNode->prev = current->prev;
            newNode->next = current;
            current->prev->next = newNode;
            current->prev = newNode;
        }
        size++;
    }


    void deleteHead(){
        if(isEmpty()){
            std::cout << "nothing to delete" << std::endl;
            return;
        }
        Node* temp = head;
        if(head == tail){
            head = nullptr;
            tail = nullptr;
        }else{
            head = head->next;
            head->prev = nullptr;
        }
        delete temp;
        size--;
    }

    void deleteTail(){
        if(isEmpty()){
            std::cout << "nothing to delete" << std::endl;
            return;
        }
        Node* temp = tail;
        if(head == tail){
            head = nullptr;
            tail = nullptr;
        }else{
            tail = tail->prev;
            tail->next = nullptr;
        }
        delete temp;
        size--;
    }

    void deleteAtPosition(int position){
        if(position < 0 || position > size){
            std::cout << "invalid position" << std::endl;
            return;
        }
        if(position == 0){
            deleteHead();
            return;
        }
        if(position == size-1){
            deleteTail();
            return;
        }
        Node* current;

        if(position <= size/2){
            current = head;
            for(int i = 0;i < position;i++){
                current = current->next;
            }
        } else{
            current = tail;
            for(int i = size-1;i>position;i--){
                current = current->prev;
            }  
        }
        current->prev->next  = current->next;
        current->next->prev = current->prev;
        delete current;
        size--;
    }

    void deleteNode(int data){
        if(isEmpty()){
            std::cout << "nothing to delete" << std:: endl;
            return;
        }
        if(head->data == data){
            deleteHead();
            return;
        }
        if(tail->data == data){
            deleteTail();
            return;
        }

        Node* current = head->next;
        while(current != nullptr && current != tail){
            if(current->data == data){
                current->prev->next = current->next;
                current->next->prev = current->prev;
                delete current;
                size--;
                return;
            }
            current = current->next;
        }
        std::cout << "unable to delete" << std::endl;
    }

    bool search(int data){
        if(isEmpty()){
            return false;
        }
        Node* current = head;
        while(current != nullptr){
            if(current->data == data){
                return true;
            }
            current = current->next;
        }
        return false;
    }

    void displayForward(){
        if(isEmpty()){
            std::cout <<"list is Empty!" << std::endl;
            return;
        }
        std::cout << "null<-" ;
        Node* current = head;
        while(current != nullptr){
            std::cout << current->data;
            if(current->next != nullptr){
                std::cout <<"<->";
            }else{
                std::cout << "->";
            }
            current = current->next;
        }
        std::cout << "null" << std::endl;
    }

    void displayReverse(){
        if(isEmpty()){
            std::cout << "List IS Empty" << std::endl;
            return;
        }
        std:: cout<< " null<- ";
        Node* current = tail;
        while(current != nullptr){
            std::cout << current->data;
            if(current->prev != nullptr){
                std::cout << "<->";
            }else{
                std::cout << "->";
            }
            current = current->prev;
        }
        std::cout << std::endl;
    }
};


int main(){
    DoublyLinkedList list;
    list.insertAtHead(10);
    list.insertAtHead(20);
    list.displayForward();
    list.insertAtTail(40);
    list.insertAtTail(80);
    list.displayForward();

    std::cout << list.getSize();
}

